package BackTracking;

public class p37解数独 {
    class Solution {
        public void solveSudoku(char[][] board) {
            backtracking(board);
        }

        public boolean backtracking(char[][] board){
            for(int i = 0; i < board.length; i++){
                for(int j = 0; j < board[0].length; j++){
                    // 遍历棋盘，遇到"."尝试放入1-9的数字
                    if(board[i][j] != '.') continue;
                    for(char k = '1'; k <= '9'; k++){
                        if(isValid(i, j, board, k)){
                            board[i][j] = k;
                            // 找到一组解直接返回
                            if(backtracking(board)) return true;
                            board[i][j] = '.'; // 回溯
                        }
                    }
                    // 九个数试完了还不行就返回false
                    return false;
                }
            }
            return true;
        }

        // 判断当前位置是否有可放的数字
        public boolean isValid(int row, int col, char[][] board, char k){
            // 同一行上有重复
            for(int i = 0; i < 9; i++){
                if(board[row][i] == k) return false;
            }
            // 同一列上有重复
            for(int i = 0; i < 9; i++){
                if(board[i][col] == k) return false;
            }
            // 九宫格内有重复
            int startRow = (row / 3) * 3;
            int startCol = (col / 3) * 3;
            for(int i = startRow; i < startRow + 3; i++){
                for(int j = startCol; j < startCol + 3; j++){
                    if(board[i][j] == k) return false;
                }
            }
            return true;
        }
    }
}
